home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / plane / _Segment1.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  5.8 KB  |  266 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _Segment1.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. //#include <LEDA/line.h>
  18.  
  19. #ifdef AMIGA
  20. #    include <LEDA/_Segment1.h>
  21. #else
  22. #    include <LEDA/Segment1.h>
  23. #endif
  24. #include <math.h>
  25. #include <ctype.h>
  26.  
  27. //static const double eps = 1e-10;
  28.  
  29.  
  30. //------------------------------------------------------------------------------
  31. // Segments 
  32. //------------------------------------------------------------------------------
  33.  
  34. Segment_rep::Segment_rep()  { count = 1; }
  35.  
  36. Segment_rep::Segment_rep(const Point& p, const Point& q) 
  37. { start = p;
  38.   end   = q;
  39.   dx = q.X()*p.W() - p.X()*q.W();
  40.   dy = q.Y()*p.W() - p.Y()*q.W();
  41.   count = 1; 
  42.     
  43. }
  44.   
  45.  
  46.  
  47. Segment::Segment() { PTR = new Segment_rep; }
  48.  
  49. Segment::Segment(const Point& x, const Point& y) 
  50. { PTR = new Segment_rep(x,y); }
  51.  
  52. Segment::Segment(const Int& x1, const Int& y1, const Int& x2, const Int& y2) 
  53. { PTR = new Segment_rep(Point(x1,y1), Point(x2,y2)); }
  54.  
  55.  
  56. /*
  57. Segment::Segment(const Point& p, double alpha, double length)
  58. { Point q = p.translate(alpha,length);
  59.   PTR  = new Segment_rep(p,q); 
  60.  }
  61.   
  62. Segment Segment::translate(double alpha, double d) const
  63. { Point p = ptr()->start.translate(alpha,d);
  64.   Point q = ptr()->end.translate(alpha,d);
  65.   return Segment(p,q);
  66.  }
  67.  
  68. Segment Segment::translate(const vector& v) const
  69. { Point p = ptr()->start.translate(v);
  70.   Point q = ptr()->end.translate(v);
  71.   return Segment(p,q);
  72.  }
  73.  
  74. */
  75.  
  76.  
  77. ostream& operator<<(ostream& out, const Segment& s) 
  78. { out << "[" << s.start() << "===" << s.end() << "]"; 
  79.   return out;
  80.  } 
  81.  
  82. /*
  83. istream& operator>>(istream& in, Segment& s) 
  84. { int x1,x2,y1,y2; 
  85.   in >> x1 >> y1 >> x2 >> y2; 
  86.   s = Segment(Point(x1,y1),Point(x2,y2)); 
  87.   return in; 
  88.  } 
  89. */
  90.  
  91. istream& operator>>(istream& in, Segment& s) 
  92. { // syntax: {[} p {===} q {]}
  93.  
  94.   Point p,q; 
  95.   char c;
  96.  
  97.   do in.get(c); while (isspace(c));
  98.   if (c != '[') in.putback(c);
  99.  
  100.   in >> p;
  101.  
  102.   do in.get(c); while (isspace(c));
  103.   while (c== '=') in.get(c);
  104.   while (isspace(c)) in.get(c);
  105.   in.putback(c);
  106.  
  107.   in >> q; 
  108.  
  109.   do in.get(c); while (c == ' ');
  110.   if (c != ']') in.putback(c);
  111.  
  112.   s = Segment(p,q); 
  113.   return in; 
  114.  
  115.  } 
  116.  
  117.  
  118. /*
  119. double Segment::angle(const Segment& s) const
  120. {
  121.   double cosfi,fi,norm;
  122.   
  123.   double dx  = ptr()->end.ptr()->x - ptr()->start.ptr()->x; 
  124.   double dy  = ptr()->end.ptr()->y - ptr()->start.ptr()->y; 
  125.  
  126.   double dxs = s.ptr()->end.ptr()->x - s.ptr()->start.ptr()->x; 
  127.   double dys = s.ptr()->end.ptr()->y - s.ptr()->start.ptr()->y; 
  128.   
  129.   cosfi=dx*dxs+dy*dys;
  130.   
  131.   norm=(dx*dx+dy*dy)*(dxs*dxs+dys*dys);
  132.  
  133.   if (norm == 0) return 0;
  134.  
  135.   cosfi /= sqrt( norm );
  136.  
  137.   if (cosfi >=  1.0 ) return 0;
  138.   if (cosfi <= -1.0 ) return M_PI;
  139.   
  140.   fi=acos(cosfi);
  141.  
  142.   if (dx*dys-dy*dxs>0) return fi;
  143.  
  144.   return -fi;
  145.  
  146. }
  147.  
  148.  
  149. double Segment::distance(const Segment& s) const
  150. { if (angle(s)!=0) return 0;
  151.   return distance(s.ptr()->start);
  152.  }
  153.  
  154. double  Segment::distance() const
  155. { return distance(Point(0,0)); }
  156.  
  157. double Segment::distance(const Point& p) const
  158. { Segment s(ptr()->start,p);
  159.   double l = s.length();
  160.   if (l==0) return 0;
  161.   else return l*sin(angle(s));
  162.  }
  163.  
  164.  
  165. double  Segment::y_proj(double x)  const
  166. { return  ptr()->start.ptr()->y - ptr()->slope * (ptr()->start.ptr()->x - x); }
  167.  
  168. double  Segment::x_proj(double y)  const
  169. { if (vertical())  return  ptr()->start.ptr()->x;
  170.   return  ptr()->start.ptr()->x - (ptr()->start.ptr()->y - y)/ptr()->slope; }
  171.  
  172. */
  173.  
  174. bool Segment::intersection(const Segment& s, Point& inter) const
  175. /* decides whether |s| and |this| segment intersect and, if so, returns the
  176. intersection in |r|. It is assumed that both segments have non-zero length */
  177. { 
  178. Int px = ptr()->start.X();
  179. Int py = ptr()->start.Y();
  180. Int pw = ptr()->start.W();
  181.  
  182. Int qx = ptr()->end.X();
  183. Int qy = ptr()->end.Y();
  184. Int qw = ptr()->end.W();
  185.  
  186. Int spx = s.start().X();
  187. Int spy = s.start().Y();
  188. Int spw = s.start().W();
  189.  
  190. Int sqx = s.end().X();
  191. Int sqy = s.end().Y();
  192. Int sqw = s.end().W();
  193.  
  194. Int A = -(py*qw - qy*pw);
  195. Int B =   px*qw - qx*pw;
  196. Int C = -(px*qy - qx*py);
  197.  
  198.  
  199. Int Aprime = -(spy*sqw - sqy*spw);
  200. Int Bprime =   spx*sqw - sqx*spw;
  201. Int Cprime = -(spx*sqy - sqx*spy);
  202.  
  203. Int cx = -(B*Cprime - C*Bprime);
  204. Int cy =   A*Cprime - C*Aprime ;
  205. Int cw = -(A*Bprime - B*Aprime);
  206.  
  207. if (cw == 0) return false;   //same slope
  208.  
  209. inter = Point(cx,cy,cw);
  210.  
  211.  
  212. /* cw is non-zero. Its sign does not matter for the test to follow.
  213.  
  214.   
  215.   if (pX*cw < cx &&  qX*cw < cx ||  pX*cw > cx  && qX*cw > cx ||
  216.    spX*cw< cx && sqX*cw < cx || spX*cw > cx && sqX*cw > cx ||
  217.    pY*cw < cy &&  qY*cw < cy ||  pY*cw > cy  && qY*cw > cy ||
  218.    spY*cw< cy && sqY*cw < cy || spY*cw > cy && sqY*cw > cy)
  219.   return false;
  220. */
  221.  
  222. /* we still need to test whether inter lies on both segments. A point lies on a segment if it compares diffently with the two endpoints of the segment */
  223.  
  224. if ((compare(start(),inter) == compare(end(),inter)) ||
  225.  (compare(s.start(),inter) == compare(s.end(),inter)))
  226. return false;
  227.  
  228. return true;
  229. }
  230.  
  231.  
  232. bool Segment::intersection_of_lines(const Segment& s, Point& inter) const
  233. { 
  234.   /* decides whether the lines induced by |s| and |this| segment 
  235.      intersect and, if so, returns the intersection in |inter|. 
  236.      It is assumed that both segments have non-zero length
  237.    */
  238.   
  239.   Int w = dy()*s.dx() - dx()*s.dy();
  240.  
  241.   if (w == 0) return false;   //same slope
  242.  
  243.   Int c1 = X2()*Y1() - X1()*Y2();
  244.   Int c2 = s.X2()*s.Y1() - s.X1()*s.Y2();
  245.  
  246.   inter = Point(dx()*c2 - s.dx()*c1, dy()*c2 - s.dy()*c1, w);
  247.  
  248.   return true;
  249. }
  250.  
  251. /*
  252. Segment Segment::rotate(double alpha) const
  253. {  double  l = length();
  254.    Point p = start();
  255.    double beta = alpha + angle();
  256.    return Segment(p,beta,l);
  257. }
  258.  
  259. Segment Segment::rotate(const Point& origin, double alpha) const
  260. {  Point p = start().rotate(origin,alpha);
  261.    Point q = end().rotate(origin,alpha);
  262.    return Segment(p,q);
  263. }
  264. */
  265.  
  266.